package d_ch12.bellmanfFord;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

import c_ch11.WeightedGraph;

public class BellmanFord {//单源路径

    private WeightedGraph G;
    private int s;
    private int[] dis;
    private int[] pre;
    private boolean hasNegCycle = false;

    public BellmanFord(WeightedGraph G, int s){

        this.G = G;

        G.validateVertex(s);
        this.s = s;

        dis = new int[G.V()];
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[s] = 0;

        pre = new int[G.V()];
        Arrays.fill(pre, -1);
       
        for(int step = 1; step < G.V(); step ++){//如果没有负权环，任意一条最短路径的步长最长是V-1，也就是说我尝试到步长V-1时一定能找到任意最短路径；若有负权环最短路径问题没有意义
        	for(int v = 0; v < G.V(); v ++)  //事实上，应该在可达且有变化的点进行广播。这儿向上转型了
                //广播(可影响范围内全部尝试更新)即全力更新，我既知道尝试到步长V-1一定找得到最短路又知道每一个步长我都全力地最大程度地无差别地进行更新了。所以这样一定可以得到所有最短路径,也一定尝试了所有路径)
        		for(int w: G.adj(v))  
                    //广播内部。为了逻辑简单，推迟了对可达且有变化的判断。
                    if(dis[v] != Integer.MAX_VALUE //可达
                       && dis[v] + G.getWeight(v, w) < dis[w]){  //且有变化(指$1) $2是定值 有变化其实就是变小了，因为只更新shorter，所以不管是从不可达变为可达，还是普通更新，是统一的。步长为1时，其实是s点从不可达变化为0。只是是初始条件设置的。
                        dis[w] = dis[v] + G.getWeight(v, w);
                        pre[w] = v;
                    }
        }

        for(int v = 0; v < G.V(); v ++)    // 检测s所在连通分量的负权环；相同的逻辑，尝试再扩展一步；
            for(int w : G.adj(v))
                if(dis[v] != Integer.MAX_VALUE &&
                   dis[v] + G.getWeight(v, w) < dis[w]) {
                    //如果没有负权环，走V-1步长得到的一定是最短路，多走一步如果产生了更新那就说明前提不成立，即有负权环。 至于为什么多走一步一定能暴露，就别再追究了。。已经意义不大了，因为不影响记忆和使用。我又不做发明带师。
                	hasNegCycle = true;
                	break;  
                }
    }

    public boolean hasNegativeCycle(){
        return hasNegCycle;
    }

    public boolean isConnectedTo(int v){//***仍然是，只在单个连通分量里有效
        G.validateVertex(v);
        return dis[v] != Integer.MAX_VALUE;
    }

    public int distTo(int v){
        G.validateVertex(v);
        if(hasNegCycle) throw new RuntimeException("exist negative cycle.");
        return dis[v];
    }

    public Iterable<Integer> path(int t){

        ArrayList<Integer> res = new ArrayList<Integer>();
        if(!isConnectedTo(t)) return res;

        int cur = t;
        while(cur != s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);

        Collections.reverse(res);
        return res;
    }

    static public void main(String[] args){
    	
//    	Iterable<Integer> test = Arrays.asList(1,2,5,7,9);
//    	System.out.println(test);
//    	Iterator<Integer> iterator = test.iterator();
//    	for(boolean hasNext=true; hasNext; hasNext = test.iterator().hasNext()){
//    		try{
//    			System.out.print(iterator.next());  //Iterator是迭代到抛异常为止，hasNext是跟着next(),直到next抛异常才返回false；
//    		}catch (Exception e) {
//			}
//    	}
    	
        WeightedGraph g = new WeightedGraph("g2_ch12.txt");
        BellmanFord bf = new BellmanFord(g, 0);
        if(!bf.hasNegativeCycle()){
            for(int v = 0; v < g.V(); v ++)
                System.out.print(bf.distTo(v) + " ");
            System.out.println();

            System.out.println(bf.path(1));
        }
        else
            System.out.println("exist negative cycle.");

        WeightedGraph g2 = new WeightedGraph("g2_ch12.txt");
        BellmanFord bf2 = new BellmanFord(g2, 0);
        if(!bf2.hasNegativeCycle()){
            for(int v = 0; v < g2.V(); v ++)
                System.out.print(bf2.distTo(v) + " ");
            System.out.println();
        }
        else
            System.out.println("exist negative cycle.");
    }
}
